package com.xk._02算法篇._02unionFind.union;

/**
 * @description: Quick Union
 * @author: xu
 * @date: 2022/10/4 20:27
 */
public class UnionFind_QU extends UnionFind{

    public UnionFind_QU(int capacity) {
        super(capacity);
    }

    //O(logn)
    // 通过parent链条不断地向上找，直到找到根节点
    @Override
    public int find(int v){
        rangeCheck(v);
        while (v != parents[v]){
            v = parents[v];
        }
        return v;
    }

    //O(logn)
    // 将 v1 的根节点都嫁接到 v2 的根节点上
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        parents[p1] = p2;
    }
}
